package algorithm.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * 快速排序
 * 1 使用第一个元素作为基准
 * 2 从右往左移动指针 （低位指针） 直至 大于基准的数 或者移动多末端 ，从左往右移动指针（高位指针）直至 小于基准的数 或者移动到最左端
 * 3 判断右指针和左指针，是否碰撞或者相交了，如果相交 直接高位指针 和 基准值换 并记录下指针的位置 作为下次递归数组的切分点
 * 否则，低位指针和高位指针交换值，再重复2，3
 */
public class QuickSortDemo1 {

  public QuickSortDemo1(int[] arr) {
    this.arr = arr;
  }

  @Test
  public void main() {
    int[] arr = {5, 2};
    QuickSortDemo1 kuaisu2 = new QuickSortDemo1(arr);
    kuaisu2.sort(0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
  }

  int[] arr;

  private void sort(int low, int hight) {
    if (low >= hight) return;
    int mid = exchange(low, hight);
    sort(low, mid - 1);
    sort(mid + 1, hight);

  }

  //排序
  private int exchange(int low, int hight) {

    int i = low;
    int j = hight;
    int value = this.arr[low]; //基准
    i++; //基准值跳过

    while (true) {
      //从low开始往右找 直到大于value 的元素或者到达hight
      for (; i <= hight; i++) {
        if (i == hight) break;//到达high了，可以停了防止下标越界
        if (this.arr[i] > value) {
          break;  //保证 arr[low~i] <= v
        }
      }
      for (; j >= low; j--) {
        if (j == low) break;//达到low了，。。。。。。
        if (this.arr[j] < value) {
          break;  //保证 v <= arr[j~hight]
        }
      }
      if (i >= j) break; //指针碰撞了和交叉了，就停止交换值

      int v = this.arr[i];
      this.arr[i] = this.arr[j];
      this.arr[j] = v;
    }

    //把基准值 和 j元素对换，就完成了一轮
    this.arr[low] = this.arr[j];
    this.arr[j] = value;
    System.out.println(low + " " + hight + " " + Arrays.toString(this.arr));
    return j; //返回
  }

}
